MS&E 336/CS 366: Computational Social Choice

Winter 2023-24

Tu, Th 1:30-2:50pm
Bldg 160, room 332

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: Tu 4-5:30 pm, Huang 305 and on zoom (link available here). Priority to in-person students till 5 and to zoom participants thereafter.
Class forum: We will use ed stem as a discussion forum. Sign up link available here.

Auditors: please sign on to the mailman list cs366-win2324-guests and let the instructor know.

You can also browse last year's class for a rough preview of this year. Please note that this year's class will be more mathematical and computational than last year, and largely skip blockchains, due to student feedback.

DESCRIPTION
"Social Choice" is the study of collective decision making, elections being the simplest example. With the advent of the Internet, polarized democratic processes, and new modes of social interaction, this field has gained renewed interest and importance. This class will be suited for graduate (and advanced undergraduate) students who want to do research in computational and algorithmic aspects of social choice, or who would like to learn more about an important application and techniques at the intersection of algorithms, game-theory, and the social sciences.

From the Course Bulletin

An in-depth treatment of algorithmic and game-theoretic issues in social choice. Topics include common voting rules and impossibility results; ordinal vs cardinal voting; market approaches to large scale decision making; voting in complex elections, including multi-winner elections and participatory budgeting; protocols for large scale negotiation and deliberation; fairness in societal decision making; algorithmic approaches to governance of modern distributed systems such as blockchains and community-mediated social networks; opinion dynamics and polarization.

Pre-reqs: Either (a) Instructor's consent or (b) Algorithms at the level of CS 161/MS&E 212; Probability at the level of MS&E 221; basic Game Theory


REQUIREMENTS
The course requirements will be:
  1. Each student will be asked to scribe one lecture (10% of the grade). Sign up link available here.
  2. Three HWs, which can be done in groups of 2-3 (40% of the grade). Given 1/25, 2/8, 2/22. Due 2/7, 2/21, 3/6 before midnight.
  3. A take-home exam based largely on HW questions (20%). Given 3/14 before midnight. Due 3/16 before 2pm.
  4. Reading 4-6 research papers in preparation for the class.
  5. All project submissions and grading etc will be on gradescope. We will use a class forum, but we are still setting it up.
  6. A project report (30%).

    Each report should be done in groups of 2-3, and should involve a survey of an open problem, along with possible directions, and some progress for small special cases (or even the full problem). The project selection will be due at the end of the 4th week of classes, but you are welcome to get an early start if you like. A preview of suggested open problems to study will be presented in the second week of classes. All material needed for the open problems will be covered by the 6th week of classes.
    -- Preliminary report due: 3/1, midnight (15%).
    -- Final report due: 3/21, midnight (15%)


HANDOUTS

READING LIST (constantly updated)
NOTE: This list is a starting point for getting an understanding of the topics covered in class, not a comprehensive survey. No attempt has been made to list all the papers, and we will sometimes list papers that provide a simpler exposition over the first papers. If you are interested in a deeper dive, these papers will serve as a good starting point.
HCSC refers to the Handbook of computational social choice, available as a downloadable pdf or print text. AGT refers to Algorithmic Game Theory, available as an online book from the Stanford Library. We will interleave introductory material and in-depth topics.

Introductory Material:
  1. A summary of voting rules. Plurality, Copeland, Borda, Ranked Pairs, Run-offs, Transferable Single Vote. The Condorcet Criterion.  HCSC Chapter 1 and 2.1-2.7, class notes. Also see the table that illustrates the complex map of voting rules and desired properties .
  2. A brief introduction to Game-theoretic implementation concepts. AGT Chapter 1, 9.1-9.4, 5.1-5.2
    1. Nash Equilibrium, Incentive Compatibility, sub-game Perfect Equilibria, and repeated games.
    2. Fisher markets.
    3. Bargaining in two person groups: Nash bargaining and Kalai–Smorodinsky bargaining.
  3. Impossibility results in strategic voting: The Gibbard-Satterthwaite theorem: a simple proof (in brief). HCSC Chapter 2.6.
  4. Getting around the Gibbard-Satterthwaite theorem: special classes of voter utilities. The Median voting rule, and “Vox Populi”. Approval Voting. HCSC Chapter 2.7.

Research Topics:
  1. Metric Distortion.
    1. The original paper on metric distortion: Copeland achieves 5
    2. The first paper to improve on 5 (technical)
    3. The first paper to achieve factor 3 (technical)
    4. A sweeping connection between distrotion and fairness
    5. A simple proof of factor 3 via Pluarilty Veto
    6. A new randomized approach to beat factor 3
    7. Utilitarian Distortion (for context)
  2. Participating Budgeting and Sequential Deliberation.
    1. The original paper on PB as an algorithmic problem: Knapsack Voting
    2. The core of the Participatory Budgeting Problem (focus on the definition of core; the results are quite technical)
    3. A class of strategy-proof mechanisms for PB
    4. Justified Representation and the Method of Equal Shares
    5. Justified representation: extensions to Participatory Budgeting with unequal project costs
    6. The complexity of Justified Representation
    7. A variant of Justified Representation with better computational characteristics
    8. A surevy on the algorithmic aspects of PB , also includes the broader societal and political science context.
    9. An introduction to sequential deliberation
    10. Possible approach towards sequential deliberation for PB
  3. Opinion Dynamics: deGroot, Attitude polarization, Schelling Segregation. Open problem: On the Convergence of the Hegselmann-Krause System.